#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void InsertSortTest()
{
	//int arr[] = { 9,2,5,10,3,7,8,4,1,6 };
	int arr[] = { 13,1,20,43,22,9,12,100,8,-21,-100 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	InsertSort(arr, sz);
	PrintArr(arr, sz);
}

void ShellSortTest()
{
	int arr[] = { 9,2,5,10,3,7,8,4,1,6 };
	//int arr[] = { 13,1,20,43,22,9,12,100,8,-21,-100 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	ShellSort(arr, sz);
	PrintArr(arr, sz);
}

void SelectSortTest()
{
	int arr[] = { 9,2,5,10,3,7,8,4,1,6 };
	//int arr[] = { 13,1,20,43,22,9,12,100,8,-21,-100 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	SelectSort(arr, sz);
	PrintArr(arr, sz);
}

void HeapSortTest()
{
	int arr[] = { 9,2,5,10,3,7,8,4,1,6 };
	//int arr[] = { 13,1,20,43,22,9,12,100,8,-21,-100 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	HeapSort(arr, sz);
	PrintArr(arr, sz);
}

void BubbleSortTest()
{
	//int arr[] = { 9,2,5,10,3,7,8,4,1,6 };
	int arr[] = { 13,1,20,43,22,9,12,100,8,-21,-100 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	BubbleSort(arr, sz);
	PrintArr(arr, sz);
}

void QuickSortTest()
{
	int arr[] = { 9,2,5,10,3,7,8,4,1,6 };
	//int arr[] = { 13,1,20,43,22,9,12,100,8,-100,-21 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	QuickSort(arr, sz);
	PrintArr(arr, sz);
}

void MergerSortTest()
{
	//int arr[] = { 9,2,5,10,3,7,8,4,1,6 };
	int arr[] = { 13,1,20,43,22,9,12,100,8,-100,-21 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	MergerSort(arr, sz);
	PrintArr(arr, sz);
}

void CountSortTest()
{
	//int arr[] = { 9,2,5,10,3,7,8,4,1,6 };
	int arr[] = { 13,1,20,43,22,9,12,100,8,-100,-21 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	CountSort(arr, sz);
	PrintArr(arr, sz);
}

void TestOP()
{
	srand((unsigned int)time(NULL));
	int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	int* a8 = (int*)malloc(sizeof(int) * N);
	if (!a1 || !a2 || !a3 || !a4 || !a5 || !a6 || !a7 || !a8) exit(1);
	for (int i = 0; i < N; i++)
	{
		*(a1 + i) = rand();
		*(a2 + i) = *(a1 + i);
		*(a3 + i) = *(a1 + i);
		*(a4 + i) = *(a1 + i);
		*(a5 + i) = *(a1 + i);
		*(a6 + i) = *(a1 + i);
		*(a7 + i) = *(a1 + i);
	}

	int begin1 = clock();
	//InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	//SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	//BubbleSort(a5, N);
	int end5 = clock();

	int begin6 = clock();
	QuickSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	MergerSort(a7, N);
	int end7 = clock();

	int begin8 = clock();
	CountSort(a8, N);
	int end8 = clock();

	int begin9 = clock();
	//...
	int end9 = clock();

	printf("IsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("BubbleSort:%d\n", end5 - begin5);
	printf("QuickSort:%d\n", end6 - begin6);
	printf("MergerSort:%d\n", end7 - begin7);
	printf("CountSort:%d\n", end8 - begin8);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
	free(a8);
}

void QuickSortNonRTest()
{
	int arr[] = { 9,2,5,10,3,7,8,4,1,6 };
	//int arr[] = { 13,1,20,43,22,9,12,100,8,-100,-21 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	QuickSortNonR(arr, sz);
	PrintArr(arr, sz);
}

void MergeSortNonRTest()
{
	int arr[] = { 9,2,5,10,3,7,8,4,1,6 };
	//int arr[] = { 13,1,20,43,22,9,12,100,8,-100,-21 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	PrintArr(arr, sz);
	MergeSortNonR(arr, sz);
	PrintArr(arr, sz);
}

int main()
{
	//InsertSortTest();
	//ShellSortTest();
	//SelectSortTest();
	//HeapSortTest();
	//BubbleSortTest();
	//QuickSortTest();
	//MergerSortTest();
	//CountSortTest();
	//TestOP();
	//QuickSortNonRTest();
	MergeSortNonRTest();
	return 0;
}
